/*
 * Copyright (C) 2013 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.math;

import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.Param;
import com.google.caliper.api.SkipThisScenarioException;
import com.google.common.primitives.Doubles;

import java.util.Random;

/**
 * Benchmarks for various algorithms for computing the mean and/or variance.
 *
 * @author Louis Wasserman
 */
public class StatsBenchmark
{

    enum MeanAlgorithm
    {
        SIMPLE
                {
                    @Override
                    double mean(double[] values)
                    {
                        double sum = 0.0;
                        for (double value : values)
                        {
                            sum += value;
                        }
                        return sum / values.length;
                    }
                },
        KAHAN
                {
                    @Override
                    double mean(double[] values)
                    {
                        double sum = 0.0;
                        double c = 0.0;
                        for (double value : values)
                        {
                            double y = value - c;
                            double t = sum + y;
                            c = (t - sum) - y;
                            sum = t;
                        }
                        return sum / values.length;
                    }
                },
        KNUTH
                {
                    @Override
                    double mean(double[] values)
                    {
                        double mean = values[0];
                        for (int i = 1; i < values.length; i++)
                        {
                            mean = mean + (values[i] - mean) / (i + 1);
                        }
                        return mean;
                    }
                };

        abstract double mean(double[] values);
    }

    static class MeanAndVariance
    {
        private final double mean;
        private final double variance;

        MeanAndVariance(double mean, double variance)
        {
            this.mean = mean;
            this.variance = variance;
        }

        @Override
        public int hashCode()
        {
            return Doubles.hashCode(mean) * 31 + Doubles.hashCode(variance);
        }
    }

    enum VarianceAlgorithm
    {
        DO_NOT_COMPUTE
                {
                    @Override
                    MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm)
                    {
                        return new MeanAndVariance(meanAlgorithm.mean(values), 0.0);
                    }
                },
        SIMPLE
                {
                    @Override
                    MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm)
                    {
                        double mean = meanAlgorithm.mean(values);
                        double sumOfSquaresOfDeltas = 0.0;
                        for (double value : values)
                        {
                            double delta = value - mean;
                            sumOfSquaresOfDeltas += delta * delta;
                        }
                        return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
                    }
                },
        KAHAN
                {
                    @Override
                    MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm)
                    {
                        double mean = meanAlgorithm.mean(values);
                        double sumOfSquaresOfDeltas = 0.0;
                        double c = 0.0;
                        for (double value : values)
                        {
                            double delta = value - mean;
                            double deltaSquared = delta * delta;
                            double y = deltaSquared - c;
                            double t = sumOfSquaresOfDeltas + deltaSquared;
                            c = (t - sumOfSquaresOfDeltas) - y;
                            sumOfSquaresOfDeltas = t;
                        }
                        return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
                    }
                },
        KNUTH
                {
                    @Override
                    MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm)
                    {
                        if (meanAlgorithm != MeanAlgorithm.KNUTH)
                        {
                            throw new SkipThisScenarioException();
                        }
                        double mean = values[0];
                        double s = 0.0;
                        for (int i = 1; i < values.length; i++)
                        {
                            double nextMean = mean + (values[i] - mean) / (i + 1);
                            s += (values[i] - mean) * (values[i] - nextMean);
                            mean = nextMean;
                        }
                        return new MeanAndVariance(mean, s / values.length);
                    }
                };

        abstract MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm);
    }

    @Param({"100", "10000"})
    int n;

    @Param
    MeanAlgorithm meanAlgorithm;
    @Param
    VarianceAlgorithm varianceAlgorithm;

    private double[][] values = new double[0x100][];

    @BeforeExperiment
    void setUp()
    {
        Random rng = new Random();
        for (int i = 0; i < 0x100; i++)
        {
            values[i] = new double[n];
            for (int j = 0; j < n; j++)
            {
                values[i][j] = rng.nextDouble();
            }
        }
    }

    @Benchmark
    int meanAndVariance(int reps)
    {
        int tmp = 0;
        for (int i = 0; i < reps; i++)
        {
            tmp += varianceAlgorithm.variance(values[i & 0xFF], meanAlgorithm).hashCode();
        }
        return tmp;
    }
}
